package 搜索;

/**
 * 有一个m*n的grid迷宫，给定一个开始位置，可以上下左右移动，返回是否可以走到右下角的格子
 * 即grid[m-1][n-1]的位置
 */
public class 迷宫问题 {

    public static void main(String[] args) {

        int[][] grid = {
                {0, 0, 0, 1},
                {0, 0, 1, 0},
                {0, 0, 1, 1},
                {1, 0, 0, 0}};
        System.out.println(searchPath(grid, 0, 0));

    }

    // 定义四个方向
    private static int[][] direction = new int[][]{{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

    public static boolean searchPath(int[][] grid, int row, int column) {
        if (row == grid.length - 1 && column == grid[0].length - 1) {
            return true;
        }
        if (grid[row][column] == 1) {
            return false;
        }
        grid[row][column] = 1;  // 走过的地方标记为墙
        boolean flag = false;
        for (int[] direct : direction) {
            int nextRow = direct[0] + row;
            int nextColumn = direct[1] + column;
            if (nextRow >= 0 && nextRow < grid.length && nextColumn >= 0 && nextColumn < grid[0].length) {
                flag |= searchPath(grid, nextRow, nextColumn);  //四个方向有一个能到达终点就行
            }
        }
        return flag;
    }

}
